package liangtWorkSpace.sort;

/**
 * @ClassName QuickSortMap
 * @Description : 功能说明
 * @Author : LiangT
 * @Date : 2020/4/17 10:42
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 非递归实现快速排序--利用棧实现
 */
public class QuickSortMap {
    public static void quickSort(int[] arry, int startIndex, int endIndex) {
        Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();

        Map rootParam = new HashMap();
        rootParam.put("startIndex", startIndex);
        rootParam.put("endIndex", endIndex);
        quickSortStack.push(rootParam);

        while (!quickSortStack.isEmpty()) {
            Map<String, Integer> param = quickSortStack.pop();

            int pivoIndex = partition(arry, param.get("startIndex"), param.get("endIndex"));
            if (param.get("startIndex") < pivoIndex - 1) {
                Map<String, Integer> leftParam = new HashMap();
                leftParam.put("startIndex", param.get("startIndex"));
                leftParam.put("endIndex", pivoIndex - 1);
                quickSortStack.push(leftParam);
            }
            if (pivoIndex + 1 < param.get("endIndex")) {
                Map<String, Integer> rightParam = new HashMap<String,
                        Integer>();
                rightParam.put("startIndex", pivoIndex + 1);
                rightParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }

    /**
     * 分治（单边循环法）
     *
     * @param arr        待交换的数组
     * @param startIndex 起始下标
     * @param endIndex   结束下标
     */
    private static int partition(int[] arr, int startIndex,
                                 int endIndex) {
        // 取第1个位置（也可以选择随机位置）的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;

        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }

        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

}
